package com.lims.algorithm.algset.heap;

/**
 * <功能简述> 斜堆
 *
 * @author lims
 * @date 2020-07-22 17:44
 */
public class SkewHeap<T extends Comparable<T>> {
    class SkewNode<T extends Comparable<T>> {
        // 关键字
        T key;
        // 左子
        SkewNode<T> left;
        // 右子
        SkewNode<T> right;

        public SkewNode(T key, SkewNode<T> left, SkewNode<T> right) {
            this.key = key;
            this.left = left;
            this.right = right;
        }

        @Override
        public String toString() {
            return "key:" + key;
        }
    }

    /**
     * 根节点
     */
    SkewNode<T> mRoot;

    /**
     * merge，大根堆合并进小根堆
     *
     * @param x 小根堆
     * @param y 大根堆
     * @return
     */
    public SkewNode<T> merge(SkewNode<T> x, SkewNode<T> y) {
        if (x == null) {
            return y;
        }
        if (y == null) {
            return x;
        }
        if (x.key.compareTo(y.key) > 0) {
            SkewNode<T> tmp = x;
            x = y;
            y = tmp;
        }

        // 合并后左右子互换
        SkewNode<T> tmp = merge(x.right, y);
        x.right = x.left;
        x.left = tmp;

        return x;
    }

    /**
     * 插入
     *
     * @param key
     */
    public void insert(T key) {
        SkewNode<T> node = new SkewNode<T>(key, null, null);

        // 如果新建结点失败，则返回。
        if (node != null) {
            this.mRoot = merge(this.mRoot, node);
        }
    }

    /**
     * 删除根结点
     * <p>
     * 返回值：
     * 返回被删除的节点的键值
     */
    public T remove() {
        if (this.mRoot == null) {
            return null;
        }

        T key = this.mRoot.key;
        SkewNode<T> l = this.mRoot.left;
        SkewNode<T> r = this.mRoot.right;

        // 删除根节点
        this.mRoot = null;
        // 合并左右子树
        this.mRoot = merge(l, r);

        return key;
    }

    /**
     * 销毁斜堆
     */
    private void destroy(SkewNode<T> heap) {
        if (heap == null)
            return;

        if (heap.left != null)
            destroy(heap.left);
        if (heap.right != null)
            destroy(heap.right);

        heap = null;
    }

    public void clear() {
        destroy(mRoot);
        mRoot = null;
    }

    /**
     * 打印"斜堆"
     * <p>
     * key        -- 节点的键值
     * direction  --  0，表示该节点是根节点;
     * -1，表示该节点是它的父结点的左孩子;
     * 1，表示该节点是它的父结点的右孩子。
     */
    private void print(SkewNode<T> heap, T key, int direction) {

        if (heap != null) {

            // heap是根节点
            if (direction == 0) {
                System.out.printf("%2d is root\n", heap.key);
            } else {
                // heap是分支节点
                System.out.printf("%2d is %2d's %6s child\n", heap.key, key, direction == 1 ? "right" : "left");
            }

            print(heap.left, heap.key, -1);
            print(heap.right, heap.key, 1);
        }
    }

    public void print() {
        if (mRoot != null) {
            print(mRoot, mRoot.key, 0);
        }
    }

    /**************************************************************/

    public static void main(String[] args) {

        int a[] = {10, 40, 24, 30, 36, 20, 12, 16};
        int b[] = {17, 13, 11, 15, 19, 21, 23};
        SkewHeap<Integer> ha = new SkewHeap<Integer>();
        SkewHeap<Integer> hb = new SkewHeap<Integer>();

        System.out.printf("== 斜堆(ha)中依次添加: ");
        for (int i = 0; i < a.length; i++) {
            System.out.printf("%d ", a[i]);
            ha.insert(a[i]);
        }
        System.out.printf("\n== 斜堆(ha)的详细信息: \n");
        ha.print();


        System.out.printf("\n== 斜堆(hb)中依次添加: ");
        for (int i = 0; i < b.length; i++) {
            System.out.printf("%d ", b[i]);
            hb.insert(b[i]);
        }
        System.out.printf("\n== 斜堆(hb)的详细信息: \n");
        hb.print();

        // 将"斜堆hb"合并到"斜堆ha"中。
        ha.merge(ha.mRoot, hb.mRoot);
        System.out.printf("\n== 合并ha和hb后的详细信息: \n");
        ha.print();
    }
}














